package william.tree;

/**
 * @author ZhangShenao
 * @date 2024/3/6
 * @description <a href="https://leetcode.cn/problems/validate-binary-search-tree/description/">...</a>
 */
public class Leetcode98_验证二叉搜索树 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 采用递归实现
     * 根据二叉搜索树定义:对于任意棵树,需要满足 根节点 > 左子树最大值 && 根节点 < 右子树最小值, 且左、右子树也需要满足该条件
     * 维护一个取值空间[min,max]
     * 遍历从根节点开始遍历二叉树,判断每个节点的值是否在取值空间内,并更新该取值空间
     * <p>
     * 时间复杂度O(N) 需要遍历一次二叉树
     * 空间复杂度O(logN) 递归栈深度
     */
    public boolean isValidBST(TreeNode root) {
        //调用递归实现
        return isValidBSTRecursion(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    /**
     * 递归实现
     * 判断以root为根的二叉树是否为二叉搜索树,并且节点的取值范围要在(min,max)范围内
     */
    private boolean isValidBSTRecursion(TreeNode root, long min, long max) {
        //递归终止条件
        if (root == null) {  //空树也是二叉搜索树
            return true;
        }

        //校验节点的取值是否在有效范围内
        if (root.val >= max || root.val <= min) {
            return false;
        }

        //递归校验左、右子树是否也为二叉搜索树,此时需要更新取值范围
        return (isValidBSTRecursion(root.left, min, root.val) && isValidBSTRecursion(root.right, root.val, max));

    }


}
